class Solution {
public:
    const int INF = 0x3f3f3f3f;

    void dfs(TreeNode* root, string& str)
    {
        if (root == nullptr)
        {
            str += "#,";
            return;
        }
        str += std::to_string(root->val) + ",";
        dfs(root->left, str);
        dfs(root->right, str);
    }
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string str;
        dfs(root, str);
        if (str.size() != 0)
            str.pop_back();
        return str;
    }

    TreeNode* dedfs(istringstream& iss)
    {
        string val;
        getline(iss, val, ',');
        if (val == "#") return nullptr;

        TreeNode* node = new TreeNode(stoi(val));
        node->left = dedfs(iss);
        node->right = dedfs(iss);
        return node;
    }
    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream iss(data);

        return dedfs(iss);
    }
};